1. Field of the Invention
The invention relates to buffer queue structures particularly with respect to utilization in the cache invalidation logic of a cache oriented computer architecture.
2. Description of the Prior Art
Present day digital computer architectures often include interconnected subsystems comprising a plurality of central processor modules, a main memory subsystem and one or more Input/Output (I/O) subsystems. The central processor modules, main memory and I/O subsystems preferably intercommunicate by a time-shared bus system intercoupling the component sections of the computer system. In this architecture, each central processor module may include a private cache into which the processor copies words from main memory utilizing the cache in performing its processes. For example, a processor may copy program instructions and data from main memory to its cache and, thereafter, execute the program task from cache. As is appreciated, cache is used in this manner to enhance performance. The cache memory is significantly faster than main memory and the processor with the cache avoids going back and forth on the bus to main memory for each instruction.
A problem recognized in such systems is that of cache consistency. The data in the cache memories and main memory must be maintained coherent and updated with respect to each other. All copies of information at a specific address in all of the memory facilities must be maintained identical. For example, if a first one of the processors executes a WRITE TO MEMORY overwriting a main memory location that had been copied by a second one of the processors into its cache, the data in that location of the cache of the second processor becomes obsolete and invalid. The cache inconsistency condition is exacerbated when, for example, an I/O subsystem streams data into main memory overwriting numerous memory locations cached by the processors.
Traditionally, computer systems with cache memories maintain data integrity by using a cache invalidation process. The process involves each cache system monitoring, or spying upon, the memory operations of the other processors and subsystems in the computer. This is conveniently accomplished by monitoring the memory write operations on the bus. When a memory write operation is detected, each cache memory system must, at some time, execute an internal cache invalidation operation or cycle. The cache invalidation cycle involves testing the contents of the cache for the specific address of the write operation that was detected. If the cache memory system determines that it contains this address, the system marks the address as invalid. The processor with the cache must update the contents of an invalid cache location before using it.
The execution time of a cache invalidation cycle occupies a significant number of bus cycles. Thus, while the invalidation process is executing, the associated processor is prevented from performing program tasks since its cache memory resources, such as the cache tag RAM accessing and invalidation resources, are busy with the invalidation process. Additionally, when the cache memory resources of a processor are occupied with a cache invalidation cycle, other processors may perform WRITES TO MEMORY that will not be detected by the busy cache system. Such an occurrence is catastrophic to the computer system since data coherency is destroyed.
In a prior computer design, when a cache invalidation cycle is in progress, the cache system puts a RETRY signal on the bus in response to a write request from another processor or subsystem, advising the other processor or subsystem to retry its memory write request at a later time. Under conditions of heavy bus traffic, the RETRY mechanism approach may prevent processors from achieving adequate bus access thereby preventing the useful work thereof. A processor may be excessively RETRYed degrading its performance. By excessively RETRYing the I/O subsystem, this approach may also seriously interfere with the I/O subsystem bus traffic thereby detrimentally impeding the entry of data into the computer system. The condition is particularly severe in an I/O subsystem burst mode where data is streamed into main memory.
Other problems of such systems and solutions thereof are described in co-pending U.S. patent application Ser. No. 08/003,352; filed Jan. 12, 1993; entitled "Inhibit Write Apparatus And Method For Preventing Bus Lockout"; and U.S. patent application Ser. No. 08/016,588; filed Jan. 11, 1993; entitled "Varying Wait Interval Retry Apparatus And Method For Preventing Bus Lockout"; both applications by T. C. White et al. and assigned to the Assignee of the present invention. Said Ser. Nos. 08/003,352 and 08/016,588 are incorporated herein by reference.
Systems of the type described may also include an invalidation buffer or queue associated with each cache system for buffering the information detected by the spying system required for specific invalidations. The invalidation process control system may then execute the process at the least inconvenient time for the associated processor. When the invalidation queue becomes full, the RETRY signal may be issued to the bus in response to attempted WRITES with the concomitant disadvantages discussed above.
The invalidation queue should be deep enough to hold sufficient writes to minimize the effect of the cache invalidation cycles on the processor performance while providing that no WRITES are lost. The queue will fill up too quickly if the depth thereof is too shallow whereby insufficient writes are held. When the queue becomes full, the invalidation process executions are mandatory and the work of the associated processor must terminate until the invalidation processing is completed and the queue is no longer full. This is denoted as a queue flushing process. Additionally, when the queue becomes full, there is an increased possibility of losing a write on the system bus. Such a situation is catastrophic to the computer system since data coherency is destroyed.
As discussed above, another consequence of the queue being full is that whenever a new write operation is detected on the system bus, it is RETRYed since there is no room in the queue. The source module of the WRITE operation is then forced to repeat the entire operation, at which time the queue may or may not have room for the new invalidation. The RETRY mechanism can significantly impede data flow on the system bus and can be so detrimental that no useful work is performed. Under such conditions, the performance of the I/O system can be seriously degraded having a detrimental effect on the entire computer system because of the impeded I/O bus traffic. The performance of the processor with the full queue is also seriously diminished as discussed above.
Conversely, it is also undesirable to configure the queue too deep since queues are expensive structures in both cost and hardware area. Additionally, the deeper the queue, the more extensive and complicated is the control logic for supporting the queue.
The depth of the queue should be an optimum size for the relative logical speeds of the incoming system bus write operations and the outgoing invalidation processes using the cache tag RAM accessing and invalidation resources. The Application Specific Integrated Circuit Very Large Scale Integration (ASIC VLSI) gate array type technologies are advantageously utilized in constructing a highly efficient invalidation queue structure. The optimum queue depth is preferably empirically determined when actually running the cache in an operating computer system utilizing the system bus or buses under maximum system conditions. However, when this can be accomplished, the ASIC device has already been designed and constructed and cannot readily be modified in any practical, rapid or cost-effective manner and without significant schedule delays. Even if optimum queue depth is achievable, should the queue become full, invalidation WRITES could be lost with the catastrophic effects discussed above. An additional disadvantage of the system described occurs because the system bus is RETRYed during the queue flushing operation. In the time required to flush a deep queue to zero, the bus can be excessively RETRYed with the concomitant disadvantages discussed above.